This paper addresses the unrelated parallel machines scheduling problem with sequence and machine dependent setup times. Its\ngoal is to minimize the makespan. The problem is solved by a combinatorial Benders decomposition. This method can be slow to\nconverge.Therefore, three procedures are introduced to accelerate its convergence.The first procedure is a newmethod that consists\nof terminating the execution of the master problem when a repeated optimal solution is found.The second procedure is based on\nthemulticut technique.The third procedure is based on the warm-start.Theimproved Benders decomposition scheme is compared\nto a mathematical formulation and a standard implementation of Benders decomposition algorithm. In the experiments, two test\nsets from the literature are used, with 240 and 600 instances with up to 60 jobs and 5 machines. For the first set the proposed\nmethod performs 21.85% on average faster than the standard implementation of the Benders algorithm. For the second set the\nproposed method failed to find an optimal solution in only 31 in 600 instances, obtained an average gap of 0.07%, and took an\naverage computational time of 377.86 s, while the best results of the other methods were 57, 0.17%, and 573.89 s, respectively.
Loading....